package arithmetic.LeetCode;

import java.util.Stack;

import utils.ListNodeUtils;
import utils.ListNodeUtils.ListNode;

/**
 * 234. 回文链表
 * 给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
 * 示例 1：
 * 输入：head = [1,2,2,1]
 * 输出：true
 *
 * 示例 2：
 * 输入：head = [1,2]
 * 输出：false
 *
 * https://leetcode.cn/problems/palindrome-linked-list/?envType=study-plan-v2&envId=top-100-liked
 * @author jiangfeng on 2023/6/12
 */
public class IsPalindrome {
    public static void main(String[] args) {
        System.out.println(new Solution().isPalindrome(ListNodeUtils.createLink(1,2,2,1)));
        System.out.println(new Solution().isPalindrome(ListNodeUtils.createLink(1,2,1)));
        System.out.println(new Solution().isPalindrome(ListNodeUtils.createLink(1,2,3,2,1)));
    }

    static class Solution {
        public boolean isPalindrome(ListNode head) {
            Stack<Integer> s = new Stack();
            ListNode fast=head,slow = head;

            while(fast!=null && fast.next!=null){
                fast = fast.next.next;
                s.push(slow.val);
                slow = slow.next;
            }

            //slow=slow.next;
            if(fast == null){
                //
            }else{
                //fast.next==null
                // 奇数.扔一个
                slow=slow.next;
            }
            while(slow!=null){
                if(s.pop()!=slow.val){
                    return false;
                }
                slow=slow.next;
            }

            return true;
        }
    }
}
